package year2023.bitwise;

public class Code04_KM {

    //一个数组中有一种数出现K次，其它数都出现了M次 M>1 K<M
    //找到出现K次的数
    public static int onlyKTimes(int[] arr, int k, int m){
        int[] t = new int[32];
        //t[0] 0位置的1出现了几个
        //t[i] i位置的1出现了几个
        for (int num: arr) {
            for (int i = 0; i <= 31; i++) {
                //优化 t[i] += (num >> i) & 1;
                if (((num >> i) & 1) != 0){
                    t[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0){//在i位置上是有1的
                ans |= (1 << i);
            }
        }
        return ans;
    }

//    public static int test(int[] arr, int k, int m){
//        HashMap<Integer,Integer> hashMap = new HashMap<>();
//        for (int num : arr) {
//            if (hashMap.containsKey(num)){
//                hashMap.put(num,hashMap.get(num) + 1);
//            }else {
//                hashMap.put(num,1);
//            }
//        }
//        for (int num : hashMap.keySet()){
//            if (hashMap.get(num) == k){
//                return num;
//            }
//        }
//        return -1;
//    }
//
//    public static int[] randomArray(int maxKinds, int range, int k, int m){
//        int ktimeNum = randomNumber(range);
//        int numKinds = (int)(Math.random() * maxKinds);
//        //k * 1 + (numKinds - 1) * m
//        int[] arr = new int[k + (numKinds - 1) * m];
//        int index = 0;
//        for (;index < k; index++){
//            arr[index] = ktimeNum;
//        }
//        numKinds--;
//        HashSet<Integer> set = new HashSet<>();
//        set.add(ktimeNum);
//        while (numKinds != 0){
//            int curNum = 0;
//            do {
//                curNum = randomNumber(range);
//            }while (set.contains(curNum));
//            set.add(curNum);
//            numKinds--;
//            for (int i = 0; i < m; i++) {
//                arr[index++] = curNum;
//            }
//        }
//        // arr 填好了
//        for (int i = 0; i < arr.length; i++){
//            int j = (int)(Math.random() * arr.length);
//            int tmp = arr[i];
//            arr[i] = arr[j];
//            arr[j] = tmp;
//        }
//        return arr;
//    }

//    //[-range ,+range]
//    public static int randomNumber(int range){
//        return ((int)(Math.random() * range) + 1) - ((int)(Math.random() * range) + 1);
//    }


    public static void main(String[] args) {
        int[] arr = {3, 1, 3, 3, 1, 1, 4, 4};
        int k = 2;
        int m = 3;
        System.out.println(onlyKTimes(arr, 2, 3));
//        int kinds = 3;
//        int range = 20;
//        int testTime = 1000;
//        int max = 9;
//        System.out.println("测试开始");
//        for (int i = 0; i < testTime; i++) {
//            int a = (int)(Math.random() * max) + 1; // a 1~9
//            int b = (int)(Math.random() * max) + 1; // b 1~9
//            int k = Math.min(a,b);
//            int m = Math.max(a,b);
//            //k < m
//            if (k == m){
//                m++;
//            }
//            int[] arr = randomArray(kinds,range,k,m);
//            int ans1 = test(arr,k,m);
//            int ans2 = onlyKTimes(arr,k,m);
//            if (ans1 != ans2){
//                System.out.println("false");
//            }
//        }
//        System.out.println("测试结束");
//
//    }
    }

}
